Del 1: Introduksjon

I denne delen skal vi bli kjent med hvordan man plotter grafer.

Oppgave 1.1

Lag en graf ved å først opprette et objekt av klassen Graph. Legg deretter til 5-10 noder ved å bruke metoden add_node() eller add_nodes_from(). Legg så til kanter mellom de nodene du ønsker ved å bruke add_edge() eller add_edges_from(). Bruk til slutt metoden draw() for å tegne grafen.

Oppgave 1.2

Man kan finne antall noder ved å bruke metoden number_of_nodes(). Prøv den ut på grafobjektet du opprettet i forrige oppgave og print resultatet.

Oppgave 1.3

På samme måte som med noder kan man finne antallet kanter i grafen med metoden number_of_edges(). Bruk den på grafen fra oppgave 1.1 til å finne antall kanter i grafen og print resultatet.

Oppgave 1.4

Opprett et GridGraph-objekt med 5 x 5 noder. Tegn korteste vei mellom node (4, 4) og (1, 2) med metoden mark_shortest_path().

Oppgave 1.5

Vi skal forsette å bruke grafen fra forrige oppgave. Fjern node (1, 3) og (2, 2) ved å bruke metoden remove_node(). Finn nå korteste vei mellom node (4, 4) og (1, 2) og tegn resultatet. (Merk at nodene ikke nødvendigvis blir tegnet på samme steder som i forrige oppgave, men den tegner en isomorf graf)

Oppgave 1.6

Hvor mange noder må minst slettes for at korteste vei mellom node (4, 4) og (1, 2) skal bli lenger enn den var i oppgave 1.5, men at det fremdeles finnes en vei?

Det må slettes minst to noder. Per nå finnes det to veier som har vekt 7. Dersom du fjerner en node fra hver av de veiene, har ny korteste vei vekt 9

Hvor mange noder må slettes for at det ikke skal eksistere noen vei mellom node (4, 4) og (1, 2), med utgangspunkt i grafen slik den er i oppgave 1.5?

Det holder å slette to noder - enten (4,3) og (3,4) eller (1,1) og (0.2)

Oppgave 1.7

Opprett et WattsStrogatz-objekt med parametre n=100, k=4 og p=0.1. Tegn så grafen, og finn korteste vei mellom node 53 og 75.

Del 2: Strukturanalyse

Oppgave 2.1

Lag følgende 4 grafer, alle med 100 noder:

Du trenger ikke tegne grafene, bare opprett et objekt for hver graf. Det kan likevel være lurt å tegne grafen for din egen del, så du vet hvordan den ser ut.

Oppgave 2.2

For hver av de fire grafene: lag et histogram som viser degree distribution.

Oppgave 2.3

Kommenter resultatene med hensyn på sårbarheter for hver av de 4 grafene i forrige oppgave.

For ba1, så er det åpenbart at hele grafen er sårbar dersom de "innerste" nodene blir svikter. Det er mange avhengigheter som er knyttet til de innerste. Det er kun løvnodene som kan fjernes uten at det setter andre noder ut av spill. Det er node degree som forteller oss hvor mange kanter noden har. ba2 har litt flere noder med høy node degree, som gjør hele systemet (som grafen skal illustrere) mindre sårbart. Den er mindre "hierarkisk", som øker "attack resistance". Til forskjell fra ba1 er den mindre avhengig av et fåtall noder ws2 er samme som ba1: mister tilgang til resten av treet når en node svikter. Forskjellen her er at grafen ikke har like mange løvnoder, dvs. svikt av en ikke-løvnode vil kutte av deler av grafen. ws3 har nesten alle noder med degree 3 eller høyere. Fordelen med dette er at hvis en node svikter, er det lite sjans for at hele/ deler av grafen svikter. ws3 har jevnere fordelt kanter. Dvs. at hvis en tilfeldig node svikter blir ikke den potensielle omveien så stor.

Oppgave 2.4

Hvordan endrer degree distribution seg for en Barabasi Albert graf seg når m øker fra 1 til 2? Forklar hvorfor.

1) Det sprer seg mer ut. Flere noder får høyere antall kanter. 2) Typetallet (og minsteverdien) byttes fra 1 til 2 Begge observasjonene forklares logisk ved at m er "antall kanter som nye noder skal få til en vilkårlig eksisterende node"

Oppgave 2.5

Hvordan endrer degree distribution seg for en Watts Strogats graf seg når k øker fra 2 til 4? Forklar hvorfor.

Som beskrevet tidligere: mange noder med 2 kanter resulterer i en svak graf ettersom de ender i en løvnode. Det er dermed ingen loop og hvis en node svikter kan en hel gren bli utilgjengelig. Når k blir 4 blir grafen derimot mye mer robust ettersom det oftere er mulig å finne en vei fra a til b (og grafen blir bygd opp slik at omveien ikke blir veldig lang).

Oppgave 2.6

Hvordan endrer degree distribution seg for en Watts Strogats graf dersom p øker? Test det ut og forklar hvorfor.

P er sannsynligheten for at en ny kant skal ta en annen kants plass. degre distrubution er det samme. Men hvis P = 0 har alle noder automatisk kanter = k

Oppgave 2.7

Hva sier degree distribution om nettverket?

Degree annoterer hvor mange kanter en gitt node har til andre noder. Degree distrubution er den såkalte "probibility distribution" av disse nodene over hele nettverket. Vi kan definere degree distribution slik: for en gitt n noder og nk av dem har k kanter , så er degree distribution for grafen: P(k)= nk/n.

Oppgave 2.8

Oppgave 2.9

For graf 4: Identifiser noder som har høy verdi av en indeks, men lav av en annen indeks. Tips: tegning illustreringen av centrality indexene for å se det ut ifra grafen. Hva blir konsekvensene dersom disse nodene feiler?

Oppgave 2.10

Konstruer et nettverk bestående av mellom 9 og 15 noder med en node som har høyest closeness centrality, og en av de laveste degree centrality verdiene. Tips: Siden grafen ikke er så stor kan det være lettere å hardkode noder og edges enn å generere de ved hjelp av en for loop.

Del 3: Analyse av Reelle nettverk

Her skal vi analysere og diskutere reelle/ simulerte nettverk.

Oppgave 3.1

I denne oppgaven skal vi analysere Uninett sitt nettverk slik det var i 2011. Klassen RealNetworkGraph tar inn en url av en fil med filtypen .graphml. Lag et objekt for kjernenettet i Norge og tegn det. Filene som kan analyseres finnes på nettsiden Topology Zoo.

Oppgave 3.2

Plot et histogram over degree distribution for nettverket til Uninett

Oppgave 3.3

For hver av de tre centrality indeksene, print gjennomsnittlig centrality i nettverket til Uninett.

Oppgave 3.4

Diskuter resultatene fra oppgave 3.2 og 3.3. Er nettverket robust? Forklar.
Hvilket av nettverkene fra del 2 ligner Uninett sitt mest på?

Vi ser at de fleste nodene har grad i området 1-4, hvor 2 er typetallet. Som nevnt i forelesning er det større risiko tilknyttet sikkerheten og robustheten til et nettverk dersom et angrep klarer å "ta ut" de nodene med høyest node-degree. Jo høyere gjennomsnittlig centrality indeks en node har, desto "viktigere" kan de sies å være for nettverket. Dermed vil en graf med lav score på avg degree (hvorav det er et fåtall noder som har mye høyere grad enn de andre) være mindre robust. Følgelig vil jeg påstå at dette nettverket er nokså robust, men med klare svakheter dersom man klarer å ta u f.eks de 10 nodene med høyest node degree. (Jeg har ikke så mye å sammenligne med her, og "hvor robust noe er" trenger litt kontekst - jeg føler i hvert fall ikke at det er noe åpenbart svar på dette uten noe videre kontekst) Den er nok likest ba2 (ganske lik ba1 også - men det har flertall node med node degree >= 2).

Oppgave 3.5

Constructed graph simulerer et reelt netverk. Den består av et kjernenett med en grid struktur, et regionalnett og et tettbebyggd aksessnett. Bruk klassen ConstructedGraph og tegn så grafen.

Oppgave 3.6

Illustrer på grafen verdien av de tre centrality indeksene. Tips: bruk de metodene som er ferdiglagde.

Oppgave 3.7

Diskuter viktigheten og robustheten til regionalnettet.

Antar at det med "regionalnett" menes de nodene som kun er navngitt med èn bokstav og ett siffer - typ "a2". Det fremkommer ved første øyekast at viktigheten til den noden som i hvert av regionalnettene har kanter til kjernenettet er meget høy (de med siffer = 0). Følgelig vil nettverkets avhengighet av disse nodene gå negativt ut over robustheten til nettverket totalt sett. Innad i selve regionalnettverket er det heller ikke så god robusthet. Her kan vi maksimalt fjerne en node før koblingen til ett av de to aksessnettverkene mistes. (F.eks vil regionalnettverket fortsatt fungere dersom "b4" fjernes, men opphøre dersom det fjernes ytterligere noder) Ved å legge til flere kanter til kjernenettverket fra andre noder i regionalnettverket, samt øke antall kanter innad i regionalnettverket vil vi oppnå et mer robust regionalnettverk.

Del 4: Feil og Angrep på nettverk

CASE: Du er en terrorist er ute etter å utføre mest mulig skade. Vi skal nå hjelpe deg med å se på hvor det er mest interessant å angripe.

Nettverket som angripes

Bruk objektet i denne oppgaven. Grafen er et utsnitt av et VDES nettverk i aksjon der båtene snakker med hverandre, satelittene og de landbaserte radiotårnene.

4.1 Analyse av nettverket

4.1.1 Sentraliteter

For å vite hvor vi skal angripe er det en fordel å vite hvor vi kan gjøre mest mulig skade. Bruk de numeriske verdiene for de forskjellige centrality målene du lærte i de tidligere delene for ut hvilken node som er den viktigste i nettverket.

4.1.2 Sentraliteter del 2

Hvis vi tar utgangspunkt i de 3 minste nodene i hver kategori. betweenness: båt 2, båt 7, båt 9 closeness: båt 2, båt 7, båt 9 degree: båt 7, båt 8, båt 9 Vi kan helt tydelig se at node 9 har minst betydning og skårer lavest i alle kategorier. Det er nok pga. det er en løvnode. Deretter kommer node 7. Grunnen til det er at selv om den har like mange node som f.eks. node 8, så er den mindre sentral og har lenger vei til andre noder (totalt sett). Til slutt har vi node 2 og 8 som bytter litt på for hver "render". Men oppsummert kan vi se at de to laveste nodene totalt sett er node 7 og 9.

4.1.3 Annen analyse

Analyser nettverket med degree distribution og kanter per node. Diskuter robustheten bassert på de nevnte målene.

Fordelen med å kun ha en node med degree 1, er at det er bare i to tilfeller hvor man ikke klarer å aksessere denne noden. Det vil selvfølgelig være store konsekvenser, men sjanser for det skjer er lav (1/7). Videre er nodene jevnt fordelt med mange kanter som fører til at en omvei ikke blir stor hvis det skal skje et angrep.

4.2 Angrep av nettverket/feil med nettverket

4.2.1 Tilfeldige feil

Bruk metoden delete_random_nodes for å angripe grafene med tilfeldige angrep.

  • Fjern én node. Tegn så grafen.
  • Fjern tre noder. Tegn så grafen
  • Random metoden her er seedet, altså vil den gi ut samme random hver gang.

    4.2.2 Enkelt angrep

    Utfør ett enkelt målrettet angrep. Velg her den metoden som gjør mest skade og begrunn hvorfor.

    4.2.3 Flere angrep

    Utfør 3 angrep totalt og utfør mest mulig skade. Sammenlign med like mange tilfeldige feil og forklar resultatet.

    Vi kan se betydelig forskjell på tilfeldige angrep sammenlignet med angrep som går etter mest skade. Alle kategoriene er lavere med taktisk angrep. Dette kan jo være litt tilfeldig, men med taktisk angrep der man regner ut verdiene etter hvert angrep vil alltid få lavere eller likt resultat som et tilfeldig angrep.

    4.2.4 Evaluering

    Prøv å evaluere angrepene som du har gjort nå med metoder fra tidligere seksjoner.

    Slik vi tolket oppgave 4.2.3 er å gjøre beregninger for å utføre mest mulig skade. Dermed brukte vi metoder for å finne hvilke noder som hadde høyest verdi i de ulike Centrality metodene: (de som skal utføres her) degree, closeness og betweeness. Det er selvfølgelig mulig for argumentasjon for hvilken type centrality som er viktigst, men nodene vi angrpe hadde høyest verdi i flere kategorier og dermed naturlig å angripe disse. Etter første angrep oppnådde vi å gjøre båt 9 utigjenglig. Etter andre angrep oppnådde vi å gjøre nettverket veldig svakt ettersom det kun er en kant som deler de to delene av grafen. Samtidig hadde båt 4 utrolig mange kanter som fører til en stor omvei ved Shortest path. Etter tredje angrep klarer vi å dele grafen i to, slik at de er utilgjenglige for hverandre.

    4.2.5 Evaluering part 2

    For å videre evaluere angrepene vil vi introdusere "noder i største partisjon" som mål. Beregn størrelsen av største partisjon og sammenlign tilfeldig angrep med målrettet ved tre noder fjernet.

    4.2.6 Evaluering part 3

    Diskuter fordeler og ulemper med noder i største partisjon som pålitelighetsmål. Er dette et fornuftig mål i vårt tilfelle?

    Fordeler: Fremtille noe abstrakt på en veldig konkret måte. Når nettverket ikke ikke gir mye informasjon kan centrality: degree, closeness og betweeness i kombinasjon med histrogram gi utrolig mye informasjon om komplektisteten. Vi kan også se hvor et angrep til utføre mest mulig skade. Fungerer bra i et lite netverk. Med 14 noder kan vi påføre mye skade (som sett over). det lønner seg derfor i vårt tilfelle. Ulemper: Det fungerer ikke bra i et utrolig stort nettverk. Gitt et nettverk med 4000 noder må man utføre veldig mange angrep før man begynner å se et resultat.

    4.2.7 Evaluering part 4

    Drøft kort viktigheten av informasjonen rundt en nettverkstopologi.

    Viktig informasjon er: størrelse til nettverket, hvor komplekst nettverket er (anatall kanter) og hvor man kan utføre mest skade. Et eksempel er et lite nettverk, men hvis alle noder går til alle er det vil et angrep utgjøre minimalt med skade. Resultatet er at hvis vi vet denne informasjonenn, kan vi vurderer om vi vil bruke tid til å angripe eller ikke. Derfor er denne informasjonen viktig å holde skjult.

    4.3 Sikring av nettverket

    4.3.1 Flere kanter

    Legg til tre kanter for å sikre flest mulig noder mot angrep. Diskuter så hvorfor du la til de kantene du gjorde og om det nå er mer robust mot angrep.

    4.3.2 Plotting av robusthet

    Antall noder i største partisjon er et eksempel på et mål for hvor mye av et nettverk som har overlevd. Plott et linjediagram (en graf) med antall noder i største komponent langs y_aksen, antall noder fjernet på x_aksen og fjern en etter en node med de 4 forskjellige angrepene.
    Lag en funksjon for denne grafen.
    Bruk ConstructedGraph nettverket og plott grafen.

    4.3.3 Sammenligning av angrepene

    Er noen av angrepene bedre enn andre? Hvordan gjør tilfeldige feil det?

    Det skal sier at random kan bli bedre, men når jeg har kjørt grafen flere ganger er den oftest dårligst. Her kan vi tydelig se at med et tilfeldig angrep til det ta lang tid før man får et resultat, sammenlignet med target attack. De tre centrality angrepene er ganske like, men vi kan utifra grafen se at closeness og betweenness er nesten identiske. Degree er derimot litt treigere.

    4.3.4 Beregning av kostnad

    Kostnaden kan måles med antall kanter per node i nettverket. Beregn kanter per node for VDES med ekstra kanter og VDES uten.

    4.3.5 Sammenligning med ekstra redundans

    Nettverket ble absolutt sikrere med redundans. Nå er det ingen noder med mindre enn 3 kanter, dvs. at hvis en node svikter, er det ikke sikkert det vil påvirke nettverket i noen grad. I tilegg la jeg til kanter mellom noder langt unna hverandre (boat9 og satalite0) dvs. at jeg oppretter ny Shortest path ikke bare for de nodene, men alle nodene rundt. Hvis vi har et nettverk med 7 noder, der alle går til alle, vil det være litt overkill. Med andre ord kommer vi til et punkt for redundans ikke påvirker i stor grad bortsett fra kostnad og øker kompleksiteten i nettverket. Man burde stille spørsmålet om det egentlig er nødvendig.

    4.3.6 Kostnad

    Diskuter hvor mye burde man sikre et nettverk med hensyn på redundans?

    Som i forrige oppgave, rendundans er kjempefint for å få ekstra funksjonalitet i tilfelle en node svikter, men nettverk blir fort kompleks med høy degree per node. Dvs. at man burde være forsiktig med å ikke gjøre nettverket for komplekst enn det trenger å være. Man må derfor finne en balanse mellom sikkerhet og kompleksistet/ kostnad.